#include <stdio.h>

//交换
void swap (int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

//维护堆的性质
void heapfy(int *arr, int len, int i)
{
    int largest = i;        //默认i为最大
    int lson = i * 2 + 1;
    int rson = i * 2 + 2;
    
    if (lson < len && arr[lson] > arr[largest]) largest = lson;
    if (rson < len && arr[rson] > arr[largest]) largest = rson;
    if (largest != i) {         //此时lson或者rson的堆性质发生改变需要heapfy()
        swap(&arr[largest], &arr[i]);
        heapfy(arr, len, largest);
    }
}


void heap_sort(int *arr, int len) 
{   //重要：
    //建堆 此时注意建堆要从后往前建立  递归的性质
    for(int i = len/2-1; i >= 0; i--) { //从最后一个堆开始堆化
        heapfy(arr, len, i);
    }
    //排序 此时从第一个开始因为只改变了一个另一条枝干是堆
    for (int i = len-1; i > 0; i--) { //i=0也可以
        swap(&arr[i], &arr[0]);
        heapfy(arr, i, 0); //此时的第二个参数相当于删除了排序后的元素 如第一次交换后 就是len-1
    }
}

int main(void)
{
    int arr[10] = {10, 1, 8, 5, 6, 7, 4, 3, 2, 9};
    int len = sizeof(arr) / sizeof(*arr);
    
    //堆排序
    heap_sort(arr, len);
    printf("heap_sort:\n");
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    putchar('\n');
    return 0;
}